using System;
using System.Collections;
using System.Text;

namespace ICommonLibrary.Collection {

    [Serializable]
    public class SequencedHashMap : IDictionary {

        [Serializable]
        private class Entry {
            private readonly object _key;
            private object _value;

            private Entry _next;
            private Entry _prev;

            public Entry(object key, object value) {
                _key = key;
                _value = value;
            }

            public object Key {
                get { return _key; }
            }

            public object Value {
                get { return _value; }
                set { _value = value; }
            }

            public Entry Next {
                get { return _next; }
                set { _next = value; }
            }

            public Entry Prev {
                get { return _prev; }
                set { _prev = value; }
            }

            public override int GetHashCode() {
                return ((_key == null ? 0 : _key.GetHashCode()) ^ (_value == null ? 0 : _value.GetHashCode()));
            }

            public override bool Equals(object obj) {
                var other = obj as Entry;
                if (other == null) return false;
                if (other == this) return true;

                return ((_key == null ? other.Key == null : _key.Equals(other.Key)) &&
                        (_value == null ? other.Value == null : _value.Equals(other.Value)));
            }

            public override string ToString() {
                return "[" + _key + "=" + _value + "]";
            }

        }


        /// <summary>
        /// Construct an empty sentinel used to hold the head (sentinel.next) and the tail (sentinal.prev)
        /// of the list. The sentinal has a <see langword="null" /> key and value
        /// </summary>
        /// <returns></returns>
        private static Entry CreateSentinel() {
            var s = new Entry(null, null);
            s.Prev = s;
            s.Next = s;
            return s;
        }

        /// <summary>
        /// Sentinel used to hold the head and tail of the list of entries
        /// </summary>
        private readonly Entry _sentinel;

        /// <summary>
        /// Map of keys to entries
        /// </summary>
        private readonly Hashtable _entries;

        /// <summary>
        /// Holds the number of modifications that have occurred to the map, excluding modifications
        /// made through a collection view's iterator.
        /// </summary>
        private long _modCount;

        /// <summary>
        /// Construct a new sequenced hash map with default initial size and load factor
        /// </summary>
        public SequencedHashMap()
            : this(0, 1.0F, null) {
        }

        /// <summary>
        /// Construct a new sequenced hash map with the specified initial size and default load factor
        /// </summary>
        /// <param name="capacity">the initial size for the hash table</param>
        public SequencedHashMap(int capacity)
            : this(capacity, 1.0F, null) {
        }

        /// <summary>
        /// Construct a new sequenced hash map with the specified initial size and load factor
        /// </summary>
        /// <param name="capacity">the initial size for the hashtable</param>
        /// <param name="loadFactor">the load factor for the hash table</param>
        public SequencedHashMap(int capacity, float loadFactor)
            : this(capacity, loadFactor, null) {
        }

        /// <summary>
        /// Construct a new sequenced hash map with the specified initial size, hash code provider
        /// and comparer
        /// </summary>
        /// <param name="capacity">the initial size for the hashtable</param>
        /// <param name="equalityComparer"></param>
        public SequencedHashMap(int capacity, IEqualityComparer equalityComparer)
            : this(capacity, 1.0F, equalityComparer) {
        }

        /// <summary>
        /// Creates an empty Hashtable with the default initial capacity and using the default load factor, 
        /// the specified hash code provider and the specified comparer
        /// </summary>
        /// <param name="equalityComparer"></param>
        public SequencedHashMap(IEqualityComparer equalityComparer)
            : this(0, 1.0F, equalityComparer) {
        }

        /// <summary>
        /// Creates an empty Hashtable with the default initial capacity and using the default load factor, 
        /// the specified hash code provider and the specified comparer
        /// </summary>
        /// <param name="capacity">the initial size for the hashtable</param>
        /// <param name="loadFactor">the load factor for the hash table</param>
        /// <param name="equalityComparer"></param>
        public SequencedHashMap(int capacity, float loadFactor, IEqualityComparer equalityComparer) {
            _sentinel = CreateSentinel();
            _entries = new Hashtable(capacity, loadFactor, equalityComparer);
        }

        /// <summary>
        /// Removes an internal entry from the linked list. THis does not remove it from the underlying
        /// map.
        /// </summary>
        /// <param name="entry"></param>
        private static void RemoveEntry(Entry entry) {
            entry.Next.Prev = entry.Prev;
            entry.Prev.Next = entry.Next;
        }

        /// <summary>
        /// Inserts a new internal entry to the tail of the linked list. This does not add the 
        /// entry to the underlying map.
        /// </summary>
        /// <param name="entry"></param>
        private void InsertEntry(Entry entry) {
            entry.Next = _sentinel;
            entry.Prev = _sentinel.Prev;
            _sentinel.Prev.Next = entry;
            _sentinel.Prev = entry;
        }

        /// <summary></summary>
        public virtual bool IsFixedSize {
            get { return false; }
        }

        /// <summary></summary>
        public virtual bool IsReadOnly {
            get { return false; }
        }

        /// <summary></summary>
        public virtual object this[object o] {
            get {
                var entry = (Entry)_entries[o];
                if (entry == null) return null;

                return entry.Value;
            }
            set {
                _modCount++;

                var e = (Entry)_entries[o];
                if (e != null) {
                    RemoveEntry(e);
                    e.Value = value;
                }
                else {
                    e = new Entry(o, value);
                    _entries[o] = e;
                }

                InsertEntry(e);
            }
        }

        /// <summary></summary>
        public virtual ICollection Keys {
            get { return new KeyCollection(this); }
        }

        /// <summary></summary>
        public virtual ICollection Values {
            get { return new ValuesCollection(this); }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="key"></param>
        /// <param name="value"></param>
        public virtual void Add(object key, object value) {
            this[key] = value;
        }

        /// <summary></summary>
        public virtual void Clear() {
            _modCount++;

            _entries.Clear();

            _sentinel.Next = _sentinel;
            _sentinel.Prev = _sentinel;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public virtual bool Contains(object key) {
            return ContainsKey(key);
        }

        /// <summary></summary>
        public virtual IDictionaryEnumerator GetEnumerator() {
            return new OrderedEnumerator(this, ReturnType.ReturnEntry);
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="key"></param>
        public virtual void Remove(object key) {
            RemoveImpl(key);
        }

        /// <summary></summary>
        public virtual int Count {
            get { return _entries.Count; }
        }

        /// <summary></summary>
        public virtual bool IsSynchronized {
            get { return false; }
        }

        /// <summary></summary>
        public virtual object SyncRoot {
            get { return this; }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="array"></param>
        /// <param name="index"></param>
        public virtual void CopyTo(Array array, int index) {
            foreach (DictionaryEntry de in this) {
                array.SetValue(de, index++);
            }
        }

        /// <summary></summary>
        IEnumerator IEnumerable.GetEnumerator() {
            return new OrderedEnumerator(this, ReturnType.ReturnEntry);
        }

        private bool IsEmpty {
            get { return _sentinel.Next == _sentinel; }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public virtual bool ContainsKey(object key) {
            return _entries.ContainsKey(key);
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="value"></param>
        /// <returns></returns>
        public virtual bool ContainsValue(object value) {
            if (value == null) {
                for (Entry pos = _sentinel.Next; pos != _sentinel; pos = pos.Next) {
                    if (pos.Value == null) return true;
                }
            }
            else {
                for (Entry pos = _sentinel.Next; pos != _sentinel; pos = pos.Next) {
                    if (value.Equals(pos.Value)) return true;
                }
            }
            return false;
        }


        private Entry First {
            get { return (IsEmpty) ? null : _sentinel.Next; }
        }

        /// <summary></summary>
        public virtual object FirstKey {
            get { return (First == null) ? null : First.Key; }
        }

        /// <summary></summary>
        public virtual object FirstValue {
            get { return (First == null) ? null : First.Value; }
        }

        private Entry Last {
            get { return (IsEmpty) ? null : _sentinel.Prev; }
        }

        /// <summary></summary>
        public virtual object LastKey {
            get { return (Last == null) ? null : Last.Key; }
        }

        /// <summary></summary>
        public virtual object LastValue {
            get { return (Last == null) ? null : Last.Value; }
        }


        /// <summary>
        /// Remove the Entry identified by the Key if it exists.
        /// </summary>
        /// <param name="key">The Key to remove.</param>
        private void RemoveImpl(object key) {
            var e = (Entry)_entries[key];
            if (e != null) {
                _entries.Remove(key);
                _modCount++;
                RemoveEntry(e);
            }
        }

        /// <summary></summary>
        public override string ToString() {
            var buf = new StringBuilder();
            buf.Append('[');
            for (Entry pos = _sentinel.Next; pos != _sentinel; pos = pos.Next) {
                buf.Append(pos.Key);
                buf.Append('=');
                buf.Append(pos.Value);
                if (pos.Next != _sentinel) {
                    buf.Append(',');
                }
            }
            buf.Append(']');

            return buf.ToString();
        }

        private class KeyCollection : ICollection {
            private readonly SequencedHashMap _parent;

            public KeyCollection(SequencedHashMap parent) {
                _parent = parent;
            }

            public int Count {
                get { return _parent.Count; }
            }

            public bool IsSynchronized {
                get { return false; }
            }

            public object SyncRoot {
                get { return this; }
            }

            public void CopyTo(Array array, int index) {
                foreach (object obj in this) {
                    array.SetValue(obj, index++);
                }
            }

            public IEnumerator GetEnumerator() {
                return new OrderedEnumerator(_parent, ReturnType.ReturnKey);
            }

            public bool Contains(object o) {
                return _parent.ContainsKey(o);
            }
        }


        private class ValuesCollection : ICollection {
            private readonly SequencedHashMap _parent;

            public ValuesCollection(SequencedHashMap parent) {
                _parent = parent;
            }

            public int Count {
                get { return _parent.Count; }
            }

            public bool IsSynchronized {
                get { return false; }
            }

            public object SyncRoot {
                get { return this; }
            }

            public void CopyTo(Array array, int index) {
                foreach (object obj in this) {
                    array.SetValue(obj, index++);
                }
            }

            public IEnumerator GetEnumerator() {
                return new OrderedEnumerator(_parent, ReturnType.ReturnValue);
            }

            public bool Contains(object o) {
                return _parent.ContainsValue(o);
            }
        }


        private enum ReturnType {
            /// <summary>
            /// Return only the Key of the DictionaryEntry
            /// </summary>
            ReturnKey,

            /// <summary>
            /// Return only the Value of the DictionaryEntry
            /// </summary>
            ReturnValue,

            /// <summary>
            /// Return the full DictionaryEntry
            /// </summary>
            ReturnEntry
        }


        private class OrderedEnumerator : IDictionaryEnumerator {
            private readonly SequencedHashMap _parent;
            private readonly ReturnType _returnType;
            private Entry _pos;
            private readonly long _expectedModCount;

            public OrderedEnumerator(SequencedHashMap parent, ReturnType returnType) {
                _parent = parent;
                _returnType = returnType;
                _pos = _parent._sentinel;
                _expectedModCount = _parent._modCount;
            }

            public object Current {
                get {
                    if (_parent._modCount != _expectedModCount) {
                        throw new InvalidOperationException("Enumerator was modified");
                    }


                    switch (_returnType) {
                        case ReturnType.ReturnKey:
                            return _pos.Key;
                        case ReturnType.ReturnValue:
                            return _pos.Value;
                        case ReturnType.ReturnEntry:
                            return new DictionaryEntry(_pos.Key, _pos.Value);
                    }
                    return null;
                }
            }

            public bool MoveNext() {
                if (_parent._modCount != _expectedModCount) {
                    throw new InvalidOperationException("Enumerator was modified");
                }
                if (_pos.Next == _parent._sentinel) {
                    return false;
                }

                _pos = _pos.Next;

                return true;
            }

            public void Reset() {
                _pos = _parent._sentinel;
            }

            public DictionaryEntry Entry {
                get { return new DictionaryEntry(_pos.Key, _pos.Value); }
            }

            public object Key {
                get { return _pos.Key; }
            }

            public object Value {
                get { return _pos.Value; }
            }

        }
    }
}